#include <bits/stdc++.h>

using namespace std;

// 分配重复整数
// 给你一个长度为n的整数数组nums，这个数组中至多有50个不同的值
// 同时你有m个顾客的订单quantity，其中整数quantity[i]是第i位顾客订单的数目
// 请你判断是否能将nums中的整数分配给这些顾客，且满足：
// 第i位顾客恰好有quantity[i]个整数、第i位顾客拿到的整数都是相同的
// 每位顾客都要满足上述两个要求，返回是否能都满足
// 测试链接 : https://leetcode.cn/problems/distribute-repeating-integers/

class Solution 
{
public:
	// 时间复杂度O(n * 3的m次方)，空间复杂度O(n * 2的m次方)
	// ppt上有时间复杂度解析
    bool canDistribute(vector<int>& nums, vector<int>& quantity) 
    {
        sort(nums.begin(), nums.end());
        int n = 1;
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] != nums[i - 1]) ++n;
        }
        // 统计相同数字的出现次数，数字是啥不重要
        // 重要的是出现次数是多少
        int cnt[n];
        memset(cnt, 0, sizeof cnt);
        int c = 1;
        for(int i = 1, j = 0; i < nums.size(); ++i)
        {
            if(nums[i] != nums[i - 1])
            {
                cnt[j++] = c;
                c = 1;
            }
            else ++c;
        }
        cnt[n - 1] = c;

        int m = quantity.size();
        int sum[1 << m];
        // sum[01010] : 满足 1 号和 3 号订单需要多少个相同的数字
        memset(sum, 0, sizeof sum);
        // 下面这个枚举是生成quantity中的每个子集，所需要数字的个数
        for(int i = 0, v, h; i < m; ++i)
        {
            v = quantity[i];
            h = 1 << i; // h 表示 i 这个订单
            for(int j = 0; j < h; ++j)
            {
                sum[h | j] = sum[j] + v;
            }
        }
        vector<vector<int>> dp(1 << m, vector<int>(n));
        return f(cnt, sum, (1 << m) - 1, 0, dp, n);
    }

    // 当前来到的数字，编号index，个数cnt[index]
	// status : 订单状态，1还需要去满足，0已经满足过了
    bool f(int* cnt, int* sum, int status, int index, vector<vector<int>>& dp, int n)
    {
        // 订单都满足了
        if(status == 0) return true;
        // status != 0，订单未全部满足，且没数字可以选了
        if(index == n) return false;
        // 缓存命中
        if(dp[status][index] != 0) return dp[status][index] == 1;
        bool ans = false;
        int k = cnt[index];
		// 这是整个实现最核心的枚举
		// j枚举了status的所有子集状态
		// 建议记住
        // j 是订单组合，其可能包含了多个订单
        // 假设 j 等于 01001，则 j 包含了 0 号订单和 3 号订单
        // 而 sum[j] 表示完成 j 这个订单组合需要相同的数字多少个
        // 注意：index 编号所代表的数字可能可以同时满足多个订单
        for(int j = status; j > 0; j = (j - 1) & status)
        {
            if(sum[j] <= k && f(cnt, sum, status ^ j, index + 1, dp, n))
            {
                ans = true;
                break;
            }
        }
        // 不选择 index 编号所代表的数字
        if(!ans)
        {
            ans = f(cnt, sum, status, index + 1, dp, n);
        }
        dp[status][index] = ans ? 1 : -1;
        return ans;
    }
};